A problem in digital image processing is the vast amount of data, expressed in binary digits or "bits," which are used to describe a digital image. Digital images are defined in terms of picture elements, or "pixels," with each pixel being the smallest unit of an image which the data processing system can process and display. Depending on the size of the image and the resolution, a low-resolution, two-dimensional, rectangular image may have as few as several tens or a hundred pixels on a side, and some high-resolution images have as many as a thousand or more pixels on a side.
Depending on a number of factors, each pixel may also have as many as eight, sixteen or more bits of data in a "continuous-tone" image. In a monochrome image, the data associated with each pixel typically identifies a "luminance" level, which is a measure of the brightness of the pixel. In a color image, the data may also identify various color components and their relative brightness in the pixel. For example, in some monochrome displays, each pixel may be black (a low luminance level) or white (a high luminance level), or it may have these plus a number of intermediate, or "gray," brightness levels. The luminance of a pixel is typically expressed as a binary encoded value, such that if, for example, eight bits are used to encode each pixel, the luminance of the pixel may have up to two hundred fifty-six (that is, 2.sup.8) different gray levels, including the black and white extremes. If the image has several colors, bits must also be used to identify the color, and, perhaps, the relative brightness level of each color in the pixel.
While an image may be defined in terms of its "continuous-tone" image values, in which each pixel is defined by eight or more bits of data, display devices such as video display terminals and printers normally can only accommodate one or at most a few bits of data for each pixel to define the luminance of the displayed pixel. Images in which a pixel's luminance is defined by one bit per pixel are termed "halftone" images, while, more generally, images in which the pixel luminance is defined by one or only a few bits of data (but fewer bits than are required for the continuous tone image) are termed "dithered" images. The continuous tone image data is processed to generate the output luminance values of the pixels ("pixel values") to define the halftone or dithered image for the display device.